\documentclass[a4paper,12pt,notitlepage]{article}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage[left=3cm,right=2cm,top=2.5cm,bottom=2.5cm]{geometry}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{remark}{Remark}

\title {An optimal online algorithm for finding all distinct subpalindromes of a string}

\author
{
	Dmitry Kosolobov, Mikhail Rubinchik\thanks{Ural Federal University}
}

\date{CSEdays 2013}

\begin{document}
\maketitle

A \emph{palindrome} is a string that is equal to its reversal. Palindromes are among the most interesting text regularities. There are many algorithmic problems concerning palindromes. In this note we consider some of them.

By a \emph{linear time} (\emph{linear space}) algorithm we mean an algorithm that processes any input string of length $n$ in $O(n)$ elementary operations (respectively, using a continuous block of memory of size $O(n)$).
By an \emph{online algorithm} we mean an algorithm that processes the input string in one pass, left to right, at most one symbol per step. All other algorithms are \emph{offline}.

There is a well known online algorithm by Manacher \cite{Manacher} that finds all maximal subpalindromes of a string in linear time and linear space (by a ``subpalindrome'' we mean a substring that is a palindrome). It is known \cite{DroubayJustinPirillo} that every string of length $n$ contains at most $n{+}1$ distinct subpalindromes, including the empty string. The following question arises naturally: \emph{can one find all distinct subpalindromes of a string in linear time and space?} In~\cite{CountingUniquePal}, this question was answered in the affirmative, but with an offline algorithm. The authors stated the existence of the corresponding online algorithm as an open problem. Our main contribution is the following result.

\begin{theorem}
Let $\Sigma$ be a finite unordered (resp., ordered) alphabet.
There exists an online algorithm which finds all distinct subpalindromes in a string over $\Sigma$ in $O(n|\Sigma|)$ (resp., $O(n\log|\Sigma|)$) time and linear space. This algorithm is optimal in the comparison based computation model.
\end{theorem}

The original Manacher's algorithm finds the shortest even-length palindrome that is a prefix of a string, but the modification presented in \cite{Stringology} computes online the longest palindromic suffix of a string. As it was proven in~\cite{CountingUniquePal}, the set of all distinct subpalindromes of a string coincides with the set of longest palindromic suffixes of all prefixes of this string. So, to solve the problem, we have to check whether the longest palindromic suffix of the current prefix of a string already occurs in the string. The key tool for this check is Ukkonen's algorithm \cite{Ukkonen} which builds online the compressed suffix tree of a string. We run Ukkonen's algorithm in parallel with the modified Manacher algorithm and use some properties of Ukkonen's algorithm to check quickly on each step whether the longest palindromic suffix of the current prefix is a new palindrome. The obtained algorithm has the required time and space complexity. Note that, unlike the algorithm of~\cite{CountingUniquePal}, our algorithm does not require the word-RAM model and works successfully in comparison based models.

To prove lower bounds, we introduce a special kind of dictionary, called \textit{cut dictionary}. It has a single operation denoted by $\mathtt{insqry}(x)$ which is equivalent to the call to $\mathtt{query}(x)$ followed by $\mathtt{insert}(x)$. We prove that if some online algorithm for finding distinct subpalindromes of a string of length $n$ over an alphabet $\Sigma$ works in $O(f(n))$ time and $O(g(n))$ space, then there exists a cut dictionary over the set $\Sigma$ which processes any sequence of $n$ calls $\mathtt{insqry}(x_1),\ldots,\mathtt{insqry}(x_n)$ in $O(f(n){+}n)$ time and $O(g(n){+}n)$ space. Then we prove the lower bounds for a cut dictionary by the standard decision tree argument. Thus we obtain the lower bound for our problem in comparison based models.

\begin{remark}
Our approach shows that it is hardly possible to design a linear time and space online algorithm for the discussed problem even in stronger natural computation models such as the word-RAM model or cellprobe model. The reason is the resource restrictions of dictionaries. However, up to the moment we have proved no nontrivial lower bounds for the cut dictionary in more sophisticated models than the comparison based model.
\end{remark}

\begin{remark}
The \emph{palindromic closure} of a string $w$ is the shortest palindrome $w'$ such that $w$ is a prefix of $w'$. It is easy to observe that the problem of finding the length of the palindromic closure of $w$ is equivalent to the problem of finding the longest palindromic suffix of $w$. It was conjectured in~\cite{CountingUniquePal} that there exists a linear time and space online algorithm finding the lengths of the palindromic closures of all prefixes of a string. The mentioned modification \cite{Stringology} of Manacher's algorithm can be easily adjusted to prove this conjecture.
\end{remark}


\begin{thebibliography}{99}
\bibitem[DJP]{DroubayJustinPirillo} X. Droubay, J. Justin, G. Pirillo. Episturmian words and some constructions
of de Luca and Rauzy, Theoret. Comput. Sci. 255 (2001) 539--553.

\bibitem[GPR]{CountingUniquePal} R. Groult, E. Prieur, G. Richomme. Counting distinct palindromes in a word in linear time,
Inform. Process. Lett. 110 (2010) 908--912.

\bibitem[Man]{Manacher} G. Manacher. A new linear-time on-line algorithm finding the smallest
initial palindrome of a string, J. ACM 22 (3) (1975) 346--351.

\bibitem[CrRy]{Stringology} M. Crochemore, W. Rytter. Jewels of Stringology, World Scientific Publishing Co. Pte. Ltd. (2002).

\bibitem[Ukk]{Ukkonen} E. Ukkonen. On-line construction of suffix trees, Algorithmica 14 (3) (1995) 249--260.

\end{thebibliography}
\end{document}
